import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Map;

/**
 * 122. 买卖股票的最佳时机 II
 * <p>
 * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
 * <p>
 * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
 * <p>
 * 返回 你能获得的 最大 利润 。
 */
public class BestTimeToBuyAndSellStock2 {


    @Test
    public void test1() {
        Assertions.assertEquals(7, maxProfit2(new int[]{7, 1, 5, 3, 6, 4}));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(4, maxProfit2(new int[]{1, 2, 3, 4, 5}));
    }

    @Test
    public void test3() {
        Assertions.assertEquals(0, maxProfit2(new int[]{7, 6, 4, 3, 1}));
    }

    int[] prices;

    //    暴力匹配算法 实现
    public int maxProfit(int[] prices) {
        this.prices = prices;
        return find(0, 0, 0);
    }

    /**
     * 思考状态转移方程
     * 状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；
     * 每一天状态可以转移，也可以不动。状态转移用下图表示：
     * 保存在 resources 文件夹下
     * （状态转移方程写在代码中）
     *
     * 说明：
     *
     * 由于不限制交易次数，除了最后一天，每一天的状态可能不变化，也可能转移；
     * 写代码的时候，可以不用对最后一天单独处理，输出最后一天，状态为 0 的时候的值即可。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * 动态规划算法实现
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }

//        一纬数组索引对应第几天
//        二纬数组索引对应着天是否卖出股票
//        数组的值代表迄今为止的利润（总收益）
        int[][] dayStatusProfit = new int[prices.length][2];

//        第0天，不买入股票
        dayStatusProfit[0][0] = 0;
//        第0天，买入股票，那么第0天的总收益就是 买股票所花掉的钱
        dayStatusProfit[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {

//          第i天卖出股票时的收益为
            dayStatusProfit[i][0] = Math.max(
                    // 第i天和第i-1天都不买入股票，那么收益就和第i-1天的收益一致
                    dayStatusProfit[i - 1][0],
//                    第i-1天买入股票时的总收益 + 第i天卖出股票时的收益
                    dayStatusProfit[i - 1][1] + prices[i]
            );

//            第i天买入股票时的收益为
            dayStatusProfit[i][1] = Math.max(
//                  第i-1天没有买入股票，那么在第i天的时候买入股票
                    dayStatusProfit[i-1][0] - prices[i],
//                    第i-1天的时候已经买入了股票，第i天的时候就什么也不用做
                    dayStatusProfit[i-1][1]
            );
        }

        int[] lastProfit = dayStatusProfit[prices.length - 1];
        return Math.max(lastProfit[0],lastProfit[1]);
    }


    /**
     * 暴力匹配算法
     *
     * @param index     当前是第几天
     * @param profitSum 迄今而至的利润总和
     * @param status    0 不持有股票，1持有股票
     * @return 从今往后的最大利润
     */
    private int find(int index, int profitSum, int status) {

        if (index >= prices.length) {
            return profitSum;
        }

        if (status == 0) {
//            买股票
            int buyProfit = find(index + 1, profitSum - prices[index], 1);

//            不买股票
            int notBuyProfit = find(index + 1, profitSum, 0);


            return Math.max(buyProfit, notBuyProfit);
        } else {
//            卖股票
            int sellProfit = find(index + 1, profitSum + prices[index], 0);

//            不卖股票
            int notSellProfit = find(index + 1, profitSum, 1);

            return Math.max(sellProfit, notSellProfit);
        }


    }
}
